#include "arraysort.h"
#include <assert.h>
#include <string.h>
#include <stdlib.h>

static void swap(char *data1, char *data2, int elem_size) {
    char *tmp;

    tmp = (char *) malloc(elem_size);
    memcpy(tmp, data1, elem_size);
    memcpy(data1, data2, elem_size);
    memcpy(data2, tmp, elem_size);
    free(tmp);
}

/*
static void swap2(char *data1, char *data2, int elem_size) {
    int i;
    char tmp;

    for (i = 0; i < elem_size; i++) {
        tmp = data1[i];
        data1[i] = data2[i];
        data2[i] = tmp;
    }
}
*/

int compare_int(const int *data1, const int *data2) {
    if (*data1 > *data2) {
        return 1;
    } else if (*data1 < *data2) {
        return -1;
    } else {
        return 0;
    }
}

int compare_string(const char **data1, const char **data2) {
    return strcmp(*data1, *data2);
}

/******************************
 * Bubble Sort                *
 ******************************/
void bubble_sort(void *array, int size, int elem_size, CompareFunc comp_func) {
    int i, j, sw;
    char *pcj, *pcj2, *pc = array;

    for (i = size - 1; i > 0; i--) {
        sw = 0;
        for (j = 0; j < i; j++) {
            pcj = pc + elem_size * j;
            pcj2 = pcj + elem_size;
            if (comp_func(pcj, pcj2) > 0) {
                swap(pcj, pcj2, elem_size);
                sw = 1;
            }
        }
        if (!sw) {
            break;
        }
    }
}

/******************************
 * Insertion Sort             *
 ******************************/
void insertion_sort(void *array, int size, int elem_size, CompareFunc comp_func) {
    int i, j;
    char *tmp, *curr, *pc = array;

    for (i = 1; i < size; i++) {
        tmp = (char *) malloc(elem_size);
        memcpy(tmp, pc + elem_size * i, elem_size);
        for (j = i - 1; j >= 0; j--) {
            curr = pc + elem_size * j;
            if (comp_func(curr, tmp) <= 0) {
                break;
            }
            /* make room */
            memcpy(curr + elem_size, curr, elem_size);
        }
        /* update current */
        curr = pc + elem_size * j;
        memcpy(curr + elem_size, tmp, elem_size);
        free(tmp);
    }
}

/******************************
 * Shell Sort                 *
 ******************************/
void shell_sort(void *array, int size, int elem_size, CompareFunc comp_func) {
    const static int stp = 3;
    const static int gap = 9;
    int h, i, j;
    char *tmp, *curr, *pc = array;

    for (h = 1; h <= size / gap; h = stp * h + 1) {
        /* find starting h */
    }
    for (; h > 0; h /= stp) {
        for (i = h; i < size; i++) {
            tmp = (char *) malloc(elem_size);
            memcpy(tmp, pc + elem_size * i, elem_size);
            for (j = i - h; j >= 0; j -= h) {
                curr = pc + elem_size * j;
                if (comp_func(curr, tmp) <= 0) {
                    break;
                }
                /* make room */
                memcpy(curr + elem_size * h, curr, elem_size);
            }
            /* update current */
            curr = pc + elem_size * j;
            memcpy(curr + elem_size * h, tmp, elem_size);
            free(tmp);
        }
    }
}

/******************************
 * Heap Sort                  *
 ******************************/
static int heap_sort_left(int i) {
    return 2 * i + 1;
}

static void heap_sort_sift(void *array,
    int size, int elem_size, CompareFunc comp_func, int index) {
    char *max_child, *root, *pc = array;
    int child_index, root_index;

	root_index = index;
    while ((child_index = heap_sort_left(root_index)) < size) {
    	root = pc + elem_size * root_index;
        max_child = pc + elem_size * child_index;
        if (child_index != size - 1
            && comp_func(max_child, max_child + elem_size) < 0) {
            child_index++;
            max_child += elem_size;
        }
        if (comp_func(root, max_child) >= 0) {
            break;
        } else {
        	swap(root, max_child, elem_size);
        }
        root_index = child_index;
    }
}

void heap_sort(void *array, int size, int elem_size, CompareFunc comp_func) {
    int i;
    char *pc = array;

    for (i = size / 2; i >= 0; i--) {
        heap_sort_sift(array, size, elem_size, comp_func, i);
    }
    for (i = size - 1; i > 0; i--) {
        swap(pc, pc + elem_size * i, elem_size);
        heap_sort_sift(array, i, elem_size, comp_func, 0);
    }
}

/******************************
 * Merge Sort                 *
 ******************************/
static void merge_sort_merge(void *array, int elem_size,
    CompareFunc comp_func, void *tmp_array, int left, int mid, int right) {
    char *pleft, *pmid, *pright, *curr1, *curr2, *tmp_all, *pc = array;

    pleft = pc + elem_size * left;
    pmid = pc + elem_size * mid;
    pright = pc + elem_size * right;
    curr1 = pleft;
    curr2 = pmid;
    tmp_all = (char *) tmp_array + elem_size * left;

    while ((curr1 <= pmid - elem_size) && (curr2 <= pright)) {
        if (comp_func(curr1, curr2) <= 0) {
            memcpy(tmp_all, curr1, elem_size);
            curr1 += elem_size;
        } else {
            memcpy(tmp_all, curr2, elem_size);
            curr2 += elem_size;
        }
        tmp_all += elem_size;
    }
    while (curr1 <= pmid - elem_size) {
        memcpy(tmp_all, curr1, elem_size);
        curr1 += elem_size;
        tmp_all += elem_size;
    }
    while (curr2 <= pright) {
        memcpy(tmp_all, curr2, elem_size);
        curr2 += elem_size;
        tmp_all += elem_size;
    }

    tmp_all = (char *) tmp_array + elem_size * left;
    memcpy(pc + elem_size * left, tmp_all, (right - left + 1) * elem_size);
}

static void merge_sort_internal(void *array, int elem_size,
    CompareFunc comp_func, void *tmp_array, int left, int right) {
    int mid;

    if (right > left) {
        mid = (right + left) / 2;
        merge_sort_internal(array, elem_size, comp_func, tmp_array, left, mid);
        merge_sort_internal(array, elem_size, comp_func, tmp_array, mid + 1, right);
        merge_sort_merge(array, elem_size, comp_func, tmp_array, left, mid + 1, right);
    }
}

void merge_sort(void *array, int size, int elem_size, CompareFunc comp_func) {
    char *tmp_array = (char *) malloc(size * elem_size);
    merge_sort_internal(array, elem_size, comp_func, tmp_array, 0, size - 1);
    free(tmp_array);
}

/******************************
 * Quick Sort                 *
 ******************************/
static void *quick_sort_median3(void *array,
    int elem_size, CompareFunc comp_func, int left, int right) {
    char *pleft, *pright, *pmid, *ppivoit, *pc = array;

    pleft = pc + elem_size * left;
    pright = pc + elem_size * right;
    pmid = pc + elem_size * ((left + right) / 2);
    if (comp_func(pleft, pmid) > 0) {
        swap(pleft, pmid, elem_size);
    }
    if (comp_func(pleft, pright) > 0) {
        swap(pleft, pright, elem_size);
    }
    if (comp_func(pmid, pright) > 0) {
        swap(pmid, pright, elem_size);
    }
    /* get pivot */
    ppivoit = pright - elem_size;
    swap(pmid, ppivoit, elem_size);
    return ppivoit;
}

/* version 1 */
static void quick_sort_insertion_sort(void *array,
    int elem_size, CompareFunc comp_func, int left, int right) {
    int i, j;
    char *tmp, *curr, *pc = array;

    for (i = left + 1; i <= right; i++) {
        tmp = (char *) malloc(elem_size);
        memcpy(tmp, pc + elem_size * i, elem_size);
        for (j = i - 1; j >= 0; j--) {
            curr = pc + elem_size * j;
            if (comp_func(curr, tmp) <= 0) {
                break;
            }
            /* make room */
            memcpy(curr + elem_size, curr, elem_size);
        }
        /* update current */
        curr = pc + elem_size * j;
        memcpy(curr + elem_size, tmp, elem_size);
        free(tmp);
    }
}

static void quick_sort_internal(void *array,
    int elem_size, CompareFunc comp_func, int left, int right) {
    /* at least 10 elements */
    const static int diff = 9;
    int i;
    char *ppivot, *pi, *pj, *pc = array;

    if (right - left < diff) {
        quick_sort_insertion_sort(array, elem_size, comp_func, left, right);
    } else {
        i = left;
        pi = pc + elem_size * left;
        pj = pc + elem_size * (right - 1);
        ppivot = quick_sort_median3(array, elem_size, comp_func, left, right);
        while (1) {
            /*
             * increase/decrease pointer in advance to avoid
             * infinite loop when array[i] == array[j] == pivot
             */
            do {
                i++;
                pi += elem_size;
            } while (comp_func(pi, ppivot) < 0);
            do {
                pj -= elem_size;
            } while (comp_func(pj, ppivot) > 0);
            /* need swap? */
            if (pi >= pj) {
                break;
            } else {
                swap(pi, pj, elem_size);
            }
        }
        swap(pi, ppivot, elem_size);
        quick_sort_internal(array, elem_size, comp_func, left, i-1);
        quick_sort_internal(array, elem_size, comp_func, i+1, right);
    }
}

void quick_sort(void *array, int size, int elem_size, CompareFunc comp_func) {
    quick_sort_internal(array, elem_size, comp_func, 0, size - 1);
}

/* version 2 */
static void quick_sort_internal2(void *array,
    int elem_size, CompareFunc comp_func, int left, int right) {
    /* at least 10 elements */
    const static int diff = 9;
    int i, l, r;
    char *ppivot, *pi, *pj, *pc = array;

    l = left;
    r = right;
    while (r - l >= diff) {
        i = l;
        pi = pc + elem_size * l;
        pj = pc + elem_size * (r - 1);
        ppivot = quick_sort_median3(array, elem_size, comp_func, l, r);
        while (1) {
            /*
             * increase/decrease pointer in advance to avoid
             * infinite loop when array[i] == array[j] == pivot
             */
            do {
                i++;
                pi += elem_size;
            } while (comp_func(pi, ppivot) < 0);
            do {
                pj -= elem_size;
            } while (comp_func(pj, ppivot) > 0);
            /* need swap? */
            if (pi >= pj) {
                break;
            } else {
                swap(pi, pj, elem_size);
            }
        }
        swap(pi, ppivot, elem_size);
        /* only recurse on smaller half */
        if (i - l < r - i) {
            quick_sort_internal(array, elem_size, comp_func, l, i-1);
            l = i + 1;
        } else {
            quick_sort_internal(array, elem_size, comp_func, i+1, r);
            r = i - 1;
        }
    }
}

void quick_sort2(void *array, int size, int elem_size, CompareFunc comp_func) {
    quick_sort_internal2(array, elem_size, comp_func, 0, size - 1);
    /* the array is nearly sorted here */
    quick_sort_insertion_sort(array, elem_size, comp_func, 0, size - 1);
}

/* version 3 */
void quick_sort3(void *array, int size, int elem_size, CompareFunc comp_func) {
    /* at least 10 elements */
    const static int diff = 9;
    int divide, stack_size, top, left, right, i;
    char *stack, *ppivot, *pi, *pj, *pc = array;

    divide = (size + 1) / (diff + 2);
    stack_size = (divide + 1) * 2;
    stack = (char *) malloc(elem_size * stack_size);
    top = 0;
    stack[top++] = size - 1;
    stack[top++] = 0;
    while (top != 0) {
        left = stack[--top];
    	right = stack[--top];
        if (right - left < diff) {
        	quick_sort_insertion_sort(array, elem_size, comp_func, left, right);
        	continue;
        }
        /* normal case */
        i = left;
        pi = pc + elem_size * left;
        pj = pc + elem_size * (right - 1);
        ppivot = quick_sort_median3(array, elem_size, comp_func, left, right);
        while (1) {
            /*
             * increase/decrease pointer in advance to avoid
             * infinite loop when array[i] == array[j] == pivot
             */
            do {
                i++;
                pi += elem_size;
            } while (comp_func(pi, ppivot) < 0);
            do {
                pj -= elem_size;
            } while (comp_func(pj, ppivot) > 0);
            /* need swap? */
            if (pi >= pj) {
                break;
            } else {
                swap(pi, pj, elem_size);
            }
        }
        swap(pi, ppivot, elem_size);
        /* push 2 divided parts */
        stack[top++] = right;
        stack[top++] = i + 1;
        stack[top++] = i - 1;
        stack[top++] = left;
    }
    free(stack);
}
